\documentclass[submission]{FPSAC2017}

\articlenumber{31}
\addbibresource{31_Liu.bib}

\usepackage{mathtools}
\usepackage{mathrsfs}
\usepackage{subfigure}
\usepackage{multicol}
\usepackage{tikz}
\usepackage{comment}

\newcommand{\bb}{\mathbb}
\newcommand{\mc}{\mathcal}
\newcommand{\ms}{\mathscr}
\newcommand{\abs}[1]{\lvert #1 \rvert}
\newcommand{\dabs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\norm}[1]{\lvert\lvert #1 \rvert\rvert}
\newcommand{\minus}{\,\backslash\,}
\newcommand{\contract}{\, / \,}

\newcommand{\weak}{\rightsquigarrow}
\renewcommand{\tilde}{\widetilde}
\newcommand{\flip}{\overline}

\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\corank}{corank}
\DeclareMathOperator{\sign}{sign}
\DeclareMathOperator{\MacP}{MacP}

\theoremstyle{definition}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{claim}[thm]{Claim}
\newtheorem{conj}[thm]{Conjecture}

\newtheorem{defn}[thm]{Definition}
\newtheorem{exam}[thm]{Example}
\newtheorem{rem}[thm]{Remark}

\numberwithin{equation}{section}

\title[Extension space conjecture]{A counterexample to the extension space conjecture for realizable oriented matroids}

\author{Gaku Liu\thanks{\href{mailto:gakuliu@math.mit.edu}{gakuliu@math.mit.edu}}}

\address{Department of Mathematics, MIT, Cambridge, USA}

\received{\today}

\abstract{The extension space conjecture of oriented matroid theory states that the space of all one-element, non-loop, non-coloop extensions of a realizable oriented matroid of rank $d$ has the homotopy type of a sphere of dimension $d-1$. We disprove this conjecture by showing the existence of a realizable uniform oriented matroid of high rank and corank 3 with disconnected extension space.}

\keywords{matroid, oriented matroid, extension space, zonotopal tiling}

\begin{document}

\maketitle

\section{Introduction}

Oriented matroids are objects which abstract the combinatorial properties of real vector arrangements and real hyperplane arrangements.
The extension space conjecture is a long-standing question in oriented matroid theory which arose as the intersection of two fundamental problems in polytope theory and oriented matroid theory: the generalized Baues conjecture and the combinatorial Grassmannian conjecture. The general theme of these problems is to better understand the extent to which combinatorial data and geometric configurations can model each other.

Rather than define oriented matroids formally, we will give a geometric description of the conjecture. Assume in this abstract that all hyperplane arrangements are central. An \emph{oriented hyperplane arrangement} is a real hyperplane arrangement in which we have oriented each hyperplane; i.e., we have chosen one side of the hyperplane to be positive and the other to be negative. We define a \emph{realizable oriented matroid} to be a combinatorial equivalence class of oriented hyperplane arrangements. A \emph{realization} of a realizable oriented matroid is a hyperplane arrangement within the equivalence class. The \emph{rank} of an oriented matroid $M$ is the dimension of an essential realization of $M$.

Fix an oriented hyperplane arrangement $A$. Suppose we want to add a new oriented hyperplane to $A$ to form a new (central) arrangement $A'$. Let $\mc E(A)$ denote the set of all possible realizable oriented matroids that $A'$ could belong to. We can put a partial order on $\mc E(A)$ by saying that $M \le M'$ if a realization for $M$ can be obtained by moving a realization for $M'$ into a more special position. The resulting poset $\mc E(A)$ is called the \emph{extension poset} of $A$.

It is easily seen that if $A$ is essential of dimension $r$, then $\mc E(A)$ is isomorphic to the face poset of the boundary of an $r$-polytope. From this we can describe the ``topology'' of $\mc E(A)$ as follows: Given a poset $\mc P$, the \emph{order complex} of $\mc P$ is the simplicial complex whose simplices are the finite chains of $\mc P$, ordered by inclusion. When we talk about the topology of a poset, we mean the topology of its order complex. For $\mc E(A)$, the order complex is isomorphic to the barycentric subdivision of the boundary of an $r$-polytope, and hence is homeomorphic to an $(r-1)$-sphere.

We now want to consider extensions of $A$ by a \emph{pseudohyperplane}, i.e. a topological deformation of hyperplane. This gives rise to a \emph{pseudohyperplane arrangement}, and the combinatorial equivalence classes of pseudohyperplane arrangements are called \emph{oriented matroids}.\footnote{We will not give a more formal definition of oriented matroids than this, but we note that this definition can be made rigorous by carefully defining what a pseudohyperplane arrangement is. Namely, the pseudohyperplanes should be tame deformations of hyperplanes and the pseudohyperplanes should intersect like normal hyperplanes; i.e.\ the intersection of a subset of the pseudohyperplanes should be the deformation of a flat.} The set of all possible oriented matroids which arise as one-pseudohyperplane extensions of $A$ is a poset as before, and this poset is an invariant of the oriented matroid $M$ of $A$. We call this the \emph{extension poset} $\mc E(M)$ of $M$, and the order complex of this poset the \emph{extension space} of $M$.

In general, $\mc E(M)$ is not homeomorphic to a sphere as is the case with $\mc E(A)$. The extension space conjecture asked if the topology of $\mc E(M)$ is still nice in the following sense.

\begin{conj} \label{ext}
If $M$ is a realizable oriented matroid of rank $r$, then $\mc E(M)$ is homotopy equivalent to a sphere of dimension $r-1$.
\end{conj}

In their paper originally introducing the conjecture, Sturmfels and Ziegler \cite{SZ93} proved the conjecture for a class of oriented matroids which they called \emph{strongly Euclidean} oriented matroids. This class includes all oriented matroids of rank at most 3 or corank at most 2.\footnote{The \emph{corank} of an oriented matroid $M$ is the number of pseudohyperplanes in a representative of $M$ minus the rank of $M$.} On the other hand, Santos \cite{San01} later showed that realizable oriented matroids which are not strongly Euclidean exist both in rank 4 and corank 3.

\cref{ext} also makes sense if one drops the hypothesis that $M$ is realizable. In this case, Mn\"{e}v and Richter-Gebert \cite{MR93} showed that this version of the conjecture is false; they constructed non-realizable oriented matroids of rank 4 with disconnected extension spaces.

In this abstract, we sketch a disproof of the extension space conjecture by showing that there exists a realizable uniform oriented matroid of high rank (possibly around $10^5$) and corank 3 with disconnected extension space. The counterexample will be described in \cref{sec:counter}.


\section{Connections to other problems}

Before describing the counterexample, we discuss the two problems mentioned at the beginning of the abstract, which are also resolved as a result of this counterexample.

\subsection{Combinatorial Grassmannians}

Let $A$ be a central, essential oriented hyperplane arrangement of dimension $n$. In the previous section, we considered extensions of $A$ by a single oriented hyperplane. We now consider extensions of $A$ by a single unoriented flat of dimension $k$ passing through the origin. The set $\mc E(k,A)$ of combinatorial equivalence classes of such extensions can be partially ordered as before; in fact, the intersection of $A$ with the new $k$-flat forms a $k$-dimensional hyperplane arrangement, so elements of $\mc E(k,A)$ can be viewed as oriented matroids. The poset $\mc E(k,A)$ is homeomorphic to the real Grassmannian $\mc G(k,n)$.

As before, we can consider a combinatorial version where we extend $A$ by a ``pseudoflat'' of dimension $k$ and look at the poset of equivalence classes of such extensions. This poset is an invariant of the oriented matroid $M$ of $A$, and is called the \emph{combinatorial Grassmannian} $\mc G(k,M)$.

Combinatorial Grassmannians can be thought of as combinatorial models for the real Grassmannian and play important roles in the theories of \emph{combinatorial differential manifolds} and \emph{matroid bundles}; see \cite{Mac93} and \cite{And99}. As before, the basic problem surrounding these objects is whether or not they are topologically similar to their real counterparts. This is captured in the following conjecture by MacPherson, Mn\"{e}v, and Ziegler \cite{MZ93}.

\begin{conj} \label{grass}
If $M$ is a realizable oriented matroid of rank $n$, then $\mc G(k,M)$ is homotopy equivalent to $\mc G(k,n)$.
\end{conj}

In the case where $k = n-1$, $\mc G(n-1,M)$ is an ``unoriented version'' of the extension space $\mc E(M)$, and in fact $\mc E(M)$ is a double cover of $\mc G(n-1,M)$. It can be shown that \cref{grass} for $k = n-1$ is equivalent to the extension space conjecture, and thus the conjecture is false in general.

There is a case of \cref{grass} which remains open and has attracted considerable attention. If $M$ is realized by the (combinatorially unique) essential $n$-dimensional hyperplane arrangement with $n$ hyperplanes, then $\mc G(k,M)$ is known as the \emph{MacPhersonian} $\MacP(k,n)$, and is the poset of all oriented matroids of rank $k$ on $n$ elements. The MacPhersonian serves as the classifying space in the theory of matroid bundles, analogous to the role played by the Grassmannian in the theory of real vector bundles. The exact relationship between real vector bundles and these combinatorial analogues remains mysterious, and an answer to \cref{grass} in the case of the MacPhersonian would go far in illuminating it. The conjecture in this case has been shown by Babson to be true for $k \le 3$ \cite{Bab93}. See \cite{And99} and \cite{AD02} for more progress on the problem.

\subsection{The generalized Baues problem}

The generalized Baues problem is a problem which arose in relation to the theory of \emph{fiber polytopes} by Billera and Sturmfels \cite{BS92}. We give a (very) vague sketch of this theory; for a comprehensive treatment, see the survey \cite{Rei99}.

Given a projection $\pi : P \to Q$ of polytopes, one can construct ``$\pi$-induced subdivisions'' of $Q$, which are polytopal subdivisions of $Q$ which are in some sense compatible with the faces of $P$ and the projection $\pi$. For example, for a certain choice of $\pi$ and $P$, the $\pi$-induced subdivisions of $Q$ are precisely all polytopal subdivisions of $Q$ whose cells' vertices are vertices of $Q$. (These subdivisions are known as \emph{polyhedral subdivisions} of $Q$.) The set of all $\pi$-induced subdivisions of $Q$ forms a poset where subdivisions are partially ordered by refinement. Within this poset, there are certain subdivisions called \emph{coherent} subdivisions; roughly speaking, these are subdivisions which can be defined globally through a linear functional. We can then construct a polytope called the \emph{fiber polytope} of $\pi$ such that the faces of this polytope are in order-preserving bijection with the coherent $\pi$-induced subdivisions of $Q$.

For example, let $Q$ be a two-dimensional polygon. It can be shown that all polyhedral subdivisions of $Q$ are coherent (or \emph{regular}), and thus the associated fiber polytope has faces in bijection with the poset of all polyhedral subdivisions of $Q$. This polytope is precisely the \emph{associahedron}, a classical polytope with a rich history.

The generalized Baues conjecture asks about the topology of the entire poset of $\pi$-induced subdivisions, including the non-coherent ones. Since this poset always has a unique maximal element, the entire poset itself is always contractible. If we remove the top element, we have the following conjecture, first posed as a problem in \cite{BKS94}.

\begin{conj} \label{baues}
Let $\mc P(\pi)$ be the poset of all $\pi$-induced subdivisions except for the top element. Then $\mc P(\pi)$ is homotopy equivalent to a sphere of dimension $\dim(P) - \dim(Q) - 1$.
\end{conj}

As with the previous conjectures, the situation is that we have some subposet (in this case, the coherent $\pi$-induced subdivisions) with a nice topology, and we want to know if this is reflected in the topology of the entire poset.

\cref{baues} was proven false by Rambau and Ziegler \cite{RZ96}. Afterwards, attention shifted to special cases of the generalized Baues conjecture, in particular the cases of polyhedral subdivisions and \emph{zonotopal tilings}. The case of polyhedral subdivisions was eventually disproved by Santos in \cite{San06}. We now discuss the conjecture for zonotopal tilings and its connection to extension spaces.

A \emph{zonotope} is the Minkowski sum of a collection of line segments, called the \emph{generating collection} for the zonotope. Formally, we will always associate a particular generating collection to a zonotope. A \emph{zonotopal tiling} of a zonotope $Z$ is a subdivision of $Z$ into other zonotopes, each of which is generated by a subcollection of the generating collection for $Z$. Zonotopal tilings are a special case of $\pi$-induced subdivisions; i.e., there is a projection $\pi : P \to Z$ such that the $\pi$-induced subdivisions are precisely the zonotopal tilings of $Z$.

Zonotopal tilings have a nice connection with \emph{liftings} of oriented matroids. Liftings of oriented matroids are the dual concept to the extensions of oriented matroids described earlier; in particular, given an oriented matroid $M$, there is a poset $\mc F(M)$ of liftings of $M$, and this poset is isomorphic to the extension poset of an oriented matroid called the \emph{dual} of $M$. The \emph{Bohne-Dress theorem} states the following.

\begin{thm}{\cite[Thm.\ 7.32]{Zie95}}
Let $Z$ be a zonotope with generating collection $V$, and let $A$ be the hyperplane arrangement with a hyperplane for each vector in $V$ perpendicular to that vector. Let $M$ be the oriented matroid of $A$. Then there is an order-preserving bijection between the set of zonotopal tilings of $Z$ (minus the top element) and $\mc F(M)$.
\end{thm}

Combined with the duality of liftings and extensions, we obtain the following.

\begin{prop}
\cref{ext} is equivalent to \cref{baues} for zonotopal tilings.
\end{prop}

Our result thus resolves this case of the generalized Baues conjecture.

\section{The counterexample and proof idea} \label{sec:counter}

We now describe the counterexample. Begin with the vector configuration $\{e_i - e_j : 1 \le i < j \le 4\}$, where $e_i$ is the $i$-th standard basis vector. Let $E_N$ be the vector configuration obtained by repeating each vector in the previous configuration $N$ times. Let $\tilde{E}_N$ be a random configuration obtained by perturbing each vector in $E_N$ by a small random displacement in the span of $E_N$. Our result is the following.

\begin{thm} \label{main}
For large enough $N$, with probability greater than 0, $\tilde{E}_N$ contains a subconfiguration $E$ with corank greater than 1 such that the oriented matroid dual to the oriented matroid of $E$ has disconnected extension space.
\end{thm}

The strategy of the proof is to show that the \emph{flip graph} associated to $\tilde{E}_N$ is disconnected. The flip graph can be defined as the highest two ``levels'' of the extension poset of the dual of $\tilde{E}_N$; its vertices are the maximal elements of this poset and its edges are the ``minimal moves'', or \emph{flips}, between them. We then use a known trick (see \cite[Lem.\ 3.1]{Rei99}, \cite[Cor.\ 4.3]{San00}) to convert disconnectedness of flip graphs to disconnectedness of entire posets. This same trick was used in the disproof of the generalized Baues conjecture for polyhedral subdivisions. (It is worth noting that the configuration $E_N$ also has disconnected flip graph \cite{Liu16a}. However, in order to make use of the above trick, the configuration we consider must be in general position.) Unfortunately, the trick only tells us that there is some subconfiguration $E \subseteq \tilde{E}_N$ whose dual oriented matroid has disconnected extension space, and does not tell us what $E$ is.

Showing that the aforementioned flip graph is disconnected is the difficult part of the proof. To do this, we use a probabilistic argument to prove the existence of certain elements of the flip graph. Roughly speaking, these elements are oriented matroids which have certain ``unflippable'' substructures; these substructures are defined locally, and a probabilistic argument is used to show that for large enough $N$, such structures must exist. The value of $N$ required for these arguments to work is roughly $10^5$. Once these elements of the flip graph are shown to exist, it is immediate that they must be in different connected components of the flip graph.

The above probabilistic argument is a much more complicated version of the one used by the author in \cite{Liu16a} to show disconnectedness of the flip graph of $E_N$. For the complete proof of \cref{main}, see the full paper \cite{Liu16b}.


\printbibliography


\end{document}
